'''
重点在于：自定义类的排序 （cmp_to_key）

描述
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
进阶：空间复杂度 O(val)，时间复杂度O(val)

输入：
[[10,30],[20,60],[80,100],[150,180]]
返回值：
[[10,60],[80,100],[150,180]]
'''

from typing import List
from functools import cmp_to_key # 含有多成员的比较就用这个，小于0就不变，大于0就交换两成员的位置

class Interval:
    def __init__(self, a=0, b=0):
        self.start = a
        self.end = b

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        res = list()
        #去除特殊情况
        if len(intervals) == 0:
            return res
        #按照区间首排序
        '''
        a.start - b.start > 0 就交换
        < 0 就不交换
        意思是，按升序排序
        '''
        intervals.sort(key=cmp_to_key(lambda a,b:a.start - b.start)) # 每两个成员之间进行比较
        #放入第一个区间
        res.append(intervals[0]) # 因为要与前一个值比较，所以要预先放入一个值
        #遍历后续区间，查看是否与末尾有重叠
        for i in range(len(intervals)):
            #区间有重叠，更新结尾
            if intervals[i].start <= res[-1].end: # 发现后面的成员的起点比前一个的终点要小的，就交换
                res[-1].end = max(res[-1].end, intervals[i].end)
            #区间没有重叠，直接加入
            else:
                res.append(intervals[i])
        return res

a = [[10,30],[20,60],[80,100],[150,180]]
in_intervals = []
for i in a:
    x1 = Interval(i[0],i[1])
    in_intervals.append(x1)
print(len(in_intervals))

s = Solution()
res = s.merge(in_intervals)
print(res)
for i in res:
    print('start:', i.start, '\tend: ', i.end)
# print(res)



